/*
 * MaximumCriticalSuccessors.java 13.06.2013
 *
 * Copyright (c) 2013 1&1 Internet AG. All rights reserved.
 *
 * $Id$
 */
package de.tum.wi.som.prio.impl;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

import de.tum.wi.som.Node;
import de.tum.wi.som.Project;
import de.tum.wi.som.prio.PriorityRule;
import de.tum.wi.som.util.PrioUtil;

/**
 * Max(CS)
 *
 * @author epollok
 *
 */
public class MaximumCriticalSuccessors implements PriorityRule {

    @Override
    public void prioritize(Project project) {
        List<Node> criticalPath = project.getCriticalPath();

        List<Node> scheduledNodes = new ArrayList<Node>();
        List<Node> remainingNodes = new ArrayList<Node>();
        remainingNodes.addAll(Arrays.asList(project.getNodes()));
        List<Node> accessibleNodes;
        Node dummyNode = new Node(0, new int[0]);

        while (!remainingNodes.isEmpty()) {
            accessibleNodes = PrioUtil.determineAccesibleNodes(scheduledNodes, project.getSource(), remainingNodes);
            if (accessibleNodes.size() == 0) {
            	System.err.println("No accessible nodes found in MaximumCriticalSuccessor");
            	return;
            }
            Node candidateNode = dummyNode;
            int maxCriticalNodes = 0;

            for (Node node : accessibleNodes) {
                Set<Node> criticalSuccessors = new HashSet<Node>();
                getCriticalSuccessors(node, criticalPath, criticalSuccessors);
                int criticalNodes = criticalSuccessors.size();
                if (candidateNode == dummyNode || criticalNodes > maxCriticalNodes) {
                    candidateNode = node;
                    maxCriticalNodes = criticalNodes;
                }
            }
            scheduledNodes.add(candidateNode);
            remainingNodes.remove(candidateNode);
        }
        project.setNodes(scheduledNodes.toArray(new Node[scheduledNodes.size()]));

    }

    private void getCriticalSuccessors(Node node, List<Node> criticalPath, Set<Node> criticalSuccessors) {
        for (Node successor : node.getSuccessors()) {
            if (criticalPath.contains(successor)) {
                criticalSuccessors.add(successor);
                getCriticalSuccessors(successor, criticalPath, criticalSuccessors);
            }
        }
    }
    
    @Override
	public String toString(){
		return "MaximumCriticalSuccessors";
	}

}
